package main.Q601_700;

import java.util.*;

public class Q641_650 {
	public static void main(String[] args) {
		System.out.println("Question641：设计循环双端队列");
		System.out.println("Question642：");
		System.out.println("Question643：子数组最大平均数Ⅰ");
		System.out.println("Question644：");
		System.out.println("Question645：错误的集合");
		System.out.println("Question646：最长数对链");
		System.out.println("Question647：回文子串");
		System.out.println("Question648：单词替换");
		System.out.println("Question649：");
		System.out.println("Question650：");
	}
}

class Question641 {
	int size;
	Deque<Integer> deque;

	public Question641(int k) {
		this.size = k;
		deque = new LinkedList<>();
	}

	public boolean insertFront(int value) {
		if (isFull()) {
			return false;
		}
		deque.addFirst(value);
		return true;
	}

	public boolean insertLast(int value) {
		if (isFull()) {
			return false;
		}
		deque.addLast(value);
		return true;
	}

	public boolean deleteFront() {
		if (isEmpty()) {
			return false;
		}
		deque.pollFirst();
		return true;
	}

	public boolean deleteLast() {
		if (isEmpty()) {
			return false;
		}
		deque.pollLast();
		return true;
	}

	public int getFront() {
		if (isEmpty()) {
			return -1;
		}
		return deque.getFirst();
	}

	public int getRear() {
		if (isEmpty()) {
			return -1;
		}
		return deque.getLast();
	}

	public boolean isEmpty() {
		return deque.isEmpty();
	}

	public boolean isFull() {
		return deque.size() == size;
	}
}

class Question643 {
	public static double findMaxAverage(int[] nums, int k) {
		int sum = 0;
		int n = nums.length;
		for (int i = 0; i < k; i++) sum += nums[i];
		int maxSum = sum;
		for (int i = k; i < n; i++) {
			sum = sum - nums[i - k] + nums[i];
			maxSum = Math.max(maxSum, sum);
		}
		return 1.0 * maxSum / k;
	}
}

class Question645 {
	public static int[] findErrorNums(int[] nums) {
		int[] errorNums = new int[2];
		int n = nums.length;
		Arrays.sort(nums);
		int prev = 0;
		for (int i = 0; i < n; i++) {
			int curr = nums[i];
			if (curr == prev) {
				errorNums[0] = prev;
			} else if (curr - prev > 1) {
				errorNums[1] = prev + 1;
			}
			prev = curr;
		}
		if (nums[n - 1] != n) {
			errorNums[1] = n;
		}
		return errorNums;
	}
}

class Question646 {
	public int findLongestChain(int[][] pairs) {
		int length = pairs.length;
		int[] dp = new int[length];
		Arrays.sort(pairs, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] != o2[0]) return o1[0] - o2[0];
				else return o1[1] - o2[1];
			}
		});
		Arrays.fill(dp, 1);
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < i; j++) {
				if (pairs[i][0] > pairs[j][1]) dp[i] = Math.max(dp[i], dp[j] + 1);
			}
		}
		return dp[length - 1];
	}
}

class Question647 {
	public int countSubstrings(String s) {
		char[] str = s.toCharArray();
		int length = str.length, count = 0;
		boolean[][] dp = new boolean[length][length];
		for (int i = length - 1; i >= 0; i--) {
			for (int j = i; j < length; j++) {
				if (i == j) dp[i][j] = true;//对角线，自身成串
				else {
					if (j - i == 1 && str[j] != str[i]) dp[i][j] = false;//i、j紧邻且不相等
					else if (j - i == 1 && str[i] == str[j]) dp[i][j] = true;//i、j紧邻且相等
					else if (j - i >= 2 && dp[i + 1][j - 1] && str[i] == str[j])
						dp[i][j] = true;//i~j的子串，须判断i+1~j-1的子串情况以及str[i]与str[j]
					else dp[i][j] = false;
				}
				if (dp[i][j]) count++;
			}
		}
		return count;
	}
}

class Question648 {
	public boolean process(String s1, String s2) {
		if (s1.length() > s2.length()) return false;
		char[] str1 = s1.toCharArray(), str2 = s2.toCharArray();
		int i = 0;
		while (i < str1.length) {
			if (str1[i] != str2[i]) return false;
			i++;
		}
		return true;
	}

	public String replaceWords(List<String> dictionary, String sentence) {
		String[] sentences = sentence.split(" ");
		for (int i = 0; i < sentences.length; i++) {
			String temp = "";
			for (int j = 0; j < dictionary.size(); j++) {
				if (process(dictionary.get(j), sentences[i]) && (temp.equals("") || temp.length() > dictionary.get(j).length()))
					temp = dictionary.get(j);
			}
			if (!temp.equals("")) sentences[i] = temp;
		}
		StringBuffer result = new StringBuffer();
		result.append(sentences[0]);
		for (int i = 1; i < sentences.length; i++) {
			result.append(" ");
			result.append(sentences[i]);
		}
		return result.toString();
	}
}